package com.hot100.t2;

/**
 * @Author Zan
 * @Create 2024/7/27 22:38
 * @ClassName: Test
 * @Description : 236. 二叉树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=problem-list-v2&envId=2cktkvj
 */

class TreeNode {
    int val;
    TreeNode left; // 左节点
    TreeNode right; // 右节点

    TreeNode(int x) {
        val = x;
    }
}

public class Test {
    public static void main(String[] args) {

    }
}

class Solution {
    /**
     * 思路展现：
     * 1. root 是前置排序
     * 2. 最简单的就是递归遍历整棵树，判断某一节点的左右子树有没有 p 和 q
     * 3. 因为找到p或q就会返回，如果left和right都不为空，说明在root的左右子树分别找到p和q，此时root就是最近公共节点；
     * 4. 那如果left和right其中一个为null，说明只在一边找到p或q，那么先找到的p或q就是最近公共节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == p || root == q || root == null)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果left 和 right都不为空，说明此时root就是最近公共节点
        // 如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之亦然。
        if (left != null && right != null) { // one in left, one in right, so this is lca
            return root;
        } else if (left != null) { // both in left
            return left;
        } else if (right != null) { // both in right
            return right;
        } else { // neither
            return null;
        }
    }
}
